#pragma once

#include <algorithm>

#include "util/pool/pool.h"

namespace hawking {
namespace indexlib {

class NumericUtil
{
public:
    static uint32_t UpperPack(uint32_t number, uint32_t pack) { return ((number + pack - 1) / pack) * pack; }
};

class Bitmap {
public:
    Bitmap(bool bSet = false, Pool* pool = nullptr) {
        if (bSet)
            _itemCount = _slotCount = INVALID_INDEX;
        else
            _itemCount = _slotCount = 0;
        _initSet = bSet;
        _data = nullptr;
        _setCount = 0;
        _mount = false;
        _pool = pool;
    }
    Bitmap(uint32_t nItemCount, bool bSet = false, Pool* pool = nullptr) {
        _pool = pool;
        _slotCount = (nItemCount + SLOT_SIZE - 1) >> 5;
        _data = IE_POOL_COMPATIBLE_NEW_VECTOR(_pool, uint32_t, _slotCount);

        _itemCount = nItemCount;
        memset(_data, bSet ? 0xFF : 0x0, _slotCount * sizeof(uint32_t));
        _setCount = bSet ? nItemCount : 0;
        _mount = false;
        _initSet = bSet;
    }
    Bitmap(const Bitmap& rhs) {
        _itemCount = rhs._itemCount;
        _setCount = rhs._setCount;
        _slotCount = rhs._slotCount;
        _initSet = rhs._initSet;
        _pool = NULL;

        if (rhs.GetData() != NULL) {
            _data = IE_POOL_COMPATIBLE_NEW_VECTOR(_pool, uint32_t, _slotCount);
            memcpy(_data, rhs._data, _slotCount * sizeof(uint32_t));
        } else {
            _data = NULL;
        }
        _mount = false;
    }
    Bitmap& operator=(const Bitmap& rhs);
    virtual ~Bitmap() {
        Clear();
    }

public:
    bool Alloc(uint32_t nItemCount, bool bSet = false);
    void Clear() {
        if (!_mount && _data != nullptr) {
            // only release _data when _pool is nullptr
            IE_POOL_COMPATIBLE_DELETE_VECTOR(_pool, _data, _slotCount);
        }
        _data = nullptr;

        _itemCount = 0;
        _setCount = 0;
    }

    uint32_t Begin() const;
    uint32_t Next(uint32_t nIndex) const;
    bool Set(uint32_t nIndex) {
        uint32_t quot = nIndex >> SLOT_SIZE_BIT_NUM;
        uint32_t rem = nIndex & SLOT_SIZE_BIT_MASK;

        if (!(_data[quot] & BITMAPOPMASK[rem])) {
            _data[quot] |= BITMAPOPMASK[rem];
            ++_setCount;
            return true;
        }
        return false;
    }
    bool Reset(uint32_t nIndex);
    void ResetAll();
    void ResetAllAfter(uint32_t nIndex);
    uint32_t GetItemCount() const { return _itemCount; }
    virtual uint32_t GetValidItemCount() const { return _itemCount; }
    uint32_t Size() const;

    uint32_t GetSetCount() const {
        return _setCount;
    }
    uint32_t GetSetCount(uint32_t begin, uint32_t end) const;

    void SetSetCount(uint32_t nCount);
    uint32_t GetUnsetCount() const;
    uint32_t GetSlotCount() const { return _slotCount; }
    uint32_t* GetData() const { return _data; }
    void Mount(uint32_t nItemCount, uint32_t* pData, bool doNotDelete = true) {
        MountWithoutRefreshSetCount(nItemCount, pData, doNotDelete);
        RefreshSetCountByScanning();
    }

    // copy bitmap in *data to *_data from startIndex
    void Copy(uint32_t startIndex, uint32_t* data, uint32_t itemCount);

    // not refreshing setcount in read-only mode
    // can improve performance
    void MountWithoutRefreshSetCount(uint32_t nItemCount, uint32_t* pData, bool doNotDelete = true);

    inline bool Test(uint32_t nIndex) const;
    inline bool IsEmpty() const;
    inline uint32_t CountBits(uint64_t value) const;
    inline uint32_t CountBits(uint32_t value, uint32_t validCount) const;
    bool HasSetData(uint32_t beginIndex, uint32_t endIndex) const;
    void ResetBetween(uint32_t beginIndex, uint32_t endIndex) const;

    Bitmap* Clone() const;

private:
    void Copy(uint32_t* dstSlotAddr, uint32_t startIndex, uint32_t* data, uint32_t itemCount);

public:
    uint32_t& operator[](uint32_t i);
    Bitmap& operator&(Bitmap& bitmap);
    Bitmap& operator&=(Bitmap& bitmap);
    Bitmap& operator|(const Bitmap& bitmap);
    Bitmap& operator|=(const Bitmap& bitmap);
    Bitmap& operator~();
    Bitmap& operator-=(Bitmap& bitmap);
    Bitmap& operator-(Bitmap& bitmap);
    bool operator==(Bitmap& bitmap);
    bool operator!=(Bitmap& bitmap);

protected:
    friend class BitmapTest;
    void RefreshSetCountByScanning() const {
        if (_data == nullptr) {
            _setCount = 0;
            return;
        }

        _setCount = 0;

        uint32_t lastSlot = _slotCount - 1;
        uint32_t testBitInLastSlot = (_itemCount & SLOT_SIZE_BIT_MASK);
        if (testBitInLastSlot) {
            _setCount = CountBits(_data[lastSlot], testBitInLastSlot);
            if (lastSlot == 0) {
                return;
            }
            --lastSlot;
        }
        if (!(lastSlot & 1)) {
            _setCount += CountBits(_data[lastSlot], 32);
            if (lastSlot == 0) {
                return;
            }
            --lastSlot;
        }

        uint64_t nData;
        uint64_t* batchAddr = (uint64_t*)_data;
        uint32_t countEnd = lastSlot / 2 + 1;
        for (uint32_t i = 0; i < countEnd; ++i) {
            if ((nData = batchAddr[i]) == 0) {
                continue;
            }
            _setCount += CountBits(nData);
        }
    }

public:
    static constexpr uint32_t BYTE_SLOT_NUM = 8;
    static constexpr uint32_t SLOT_SIZE = BYTE_SLOT_NUM * sizeof(uint32_t);
    static constexpr uint32_t SLOT_SIZE_BIT_NUM = 5;
    static constexpr uint32_t SLOT_SIZE_BIT_MASK = 0x1F;
    static constexpr uint32_t INVALID_INDEX = 0xFFFFFFFF;
    static constexpr uint32_t BITMAPOPMASK[SLOT_SIZE] = {
        0x80000000, 0x40000000, 0x20000000, 0x10000000, 0x08000000, 0x04000000, 0x02000000, 0x01000000,
        0x00800000, 0x00400000, 0x00200000, 0x00100000, 0x00080000, 0x00040000, 0x00020000, 0x00010000,
        0x00008000, 0x00004000, 0x00002000, 0x00001000, 0x00000800, 0x00000400, 0x00000200, 0x00000100,
        0x00000080, 0x00000040, 0x00000020, 0x00000010, 0x00000008, 0x00000004, 0x00000002, 0x00000001
    };

    static int32_t GetSlotCount(int32_t docCount) { return (docCount + SLOT_SIZE - 1) / SLOT_SIZE; }

    static uint32_t GetDumpSize(uint32_t bitCount)
    {
        return NumericUtil::UpperPack(bitCount, SLOT_SIZE) / BYTE_SLOT_NUM;
    }

protected:
    uint32_t _itemCount;
    uint32_t _slotCount;
    uint32_t* _data;
    Pool* _pool;
    mutable uint32_t _setCount;
    bool _mount;
    bool _initSet;
};

///////////////////////////////////////////////////
// inline functions
inline bool Bitmap::Test(uint32_t nIndex) const
{
    uint32_t quot = nIndex >> SLOT_SIZE_BIT_NUM;
    uint32_t rem = nIndex & SLOT_SIZE_BIT_MASK;

    return (_data[quot] & BITMAPOPMASK[rem]) != 0;
}

inline bool Bitmap::IsEmpty() const { return _setCount == 0; }

inline uint32_t Bitmap::CountBits(uint64_t value) const
{
    value = value - ((value >> 1) & 0x5555555555555555);
    value = (value & 0x3333333333333333) + ((value >> 2) & 0x3333333333333333);

    return (uint32_t)((((value + (value >> 4)) & 0xF0F0F0F0F0F0F0F) * 0x101010101010101) >> 56);
    return value;
}

inline uint32_t Bitmap::CountBits(uint32_t value, uint32_t validCount) const
{
    uint32_t count = 0;
    for (uint32_t i = 0; value != 0 && i < validCount; i++) {
        if ((value & BITMAPOPMASK[0]) != 0) {
            count++;
        }
        value <<= 1;
    }
    return count;
}

inline void Bitmap::MountWithoutRefreshSetCount(uint32_t nItemCount, uint32_t* pData, bool doNotDelete)
{
    _data = pData;
    _mount = doNotDelete;
    _itemCount = nItemCount;
    _slotCount = (nItemCount + SLOT_SIZE - 1) >> 5;
}

inline bool Bitmap::Reset(uint32_t nIndex)
{
    if (nIndex >= _itemCount) {
        return false;
    }
    uint32_t quot = nIndex >> SLOT_SIZE_BIT_NUM;
    uint32_t rem = nIndex & SLOT_SIZE_BIT_MASK;

    if (_data[quot] & BITMAPOPMASK[rem]) {
        _data[quot] &= ~BITMAPOPMASK[rem];
        --_setCount;
        return true;
    }
    return false;
}

///////////////////////////////////////////////////////////////////////////////////////

static size_t HASHMAP_STEPTABLE[] = {
    6,        1543,     3079,     6151,     12289,    24593,    49157,    98317,    196613,   393241,   786433,
    1572869,  3145739,  6291469,  12582917, 12582919, 12582929, 12582967, 12582971, 12582991, 12583003, 12583007,
    12583027, 12583031, 12583037, 12583061, 12583063, 12583091, 12583099, 12583121, 12583157, 12583159, 12583171,
    12583177, 12583183, 12583211, 12583217, 12583237, 12583273, 12583297, 12583327, 12583379, 12583397, 12583409,
    12583423, 12583429, 12583463, 12583469, 12583481, 12583499, 12583511, 12583513, 12583517, 12583523, 12583559,
    12583561, 12583573, 12583577, 12583583, 12583591, 12583601, 12583603, 12583607, 12583609, 12583657, 12583661,
    12583693, 12583699, 12583721, 12583741, 12583759, 12583777, 12583787, 12583789, 12583817};

static uint32_t HASHMAP_STEP_COUNT = sizeof(HASHMAP_STEPTABLE) / sizeof(HASHMAP_STEPTABLE[0]);

template <typename T, typename Pool>
class HashBucket {
public:
    const static size_t FACTOR_N = 2;

    struct Block {
        Block(size_t n) : size(n), capacity(0), prev(nullptr), next(nullptr) {
            end = begin + n;
        }

        void MountBitMap(uint32_t* data, uint32_t itemCount) {
            bitmap.Mount(itemCount, data, true);
        }

        size_t size;
        size_t capacity;
        Bitmap bitmap;
        Block* prev;
        Block* next;
        T* end;
        T begin[0];
    };

public:
    HashBucket(Pool* pool, size_t init_size)
        : block_(nullptr)
        , init_size_(init_size)
        , block_count_(0)
        , size_(0)
        , mem_pool_(pool) {}

    ~HashBucket() {
        Clear();
    }

public:
    Block* GetFirstBlock()
    {
        Block* cur = block_;
        if (cur == nullptr)
            return nullptr;
        while (cur->prev != nullptr) {
            cur = cur->prev;
        }

        return cur;
    }

    const Block* GetFirstBlock() const {
        return const_cast<HashBucket*>(this)->GetFirstBlock();
    }

    Block* GetLastBlock() { 
        return block_;
    }

    const Block* GetLastBlock() const {
        return block_;
    }

    size_t GetNumBlocks() const {
        return block_count_;
    }

    size_t Size() const {
        return size_;
    }

    static size_t GetNextBlockSize(size_t alloc_size) {
        size_t* begin = HASHMAP_STEPTABLE;
        size_t* end = begin + HASHMAP_STEP_COUNT;
        size_t* iter = std::upper_bound(begin, end, alloc_size);
        if (iter != end) {
            return *iter;
        } else {
            return HASHMAP_STEPTABLE[HASHMAP_STEP_COUNT - 1];
        }
    }

    void AddBlock() {
        size_t alloc_elem_size = block_ == nullptr ? init_size_ : block_->size;
        alloc_elem_size = GetNextBlockSize(alloc_elem_size);
        int32_t slotCount = Bitmap::GetSlotCount(alloc_elem_size);
        char* p = (char*)mem_pool_->Allocate(alloc_elem_size * sizeof(T) + sizeof(Block) + slotCount * sizeof(uint32_t));
        Block* block = new (p) Block(alloc_elem_size);
        p += alloc_elem_size * sizeof(T) + sizeof(Block);
        std::memset(p, 0, slotCount * sizeof(uint32_t));
        block->MountBitMap((uint32_t*)p, (uint32_t)alloc_elem_size);

        __asm__ __volatile__("" ::: "memory");
        AddBlock(block);
    }

    void AddBlock(Block* x)
    {
        x->prev = block_;
        if (block_ != nullptr)
            block_->next = x;

        __asm__ __volatile__("" ::: "memory");
        block_ = x;
        size_ += block_->size;
        ++block_count_;
    }

    void Clear()
    {
        block_ = nullptr;
        size_ = 0;
        block_count_ = 0;
    }

private:
    Block* block_;
    size_t init_size_;
    size_t block_count_;
    size_t size_;
    Pool* mem_pool_;
};

}
}
